import { preOrder } from "@/sources/Tree/BSTree/morris";

/**
 * https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
 * 二叉树展开为链表
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。
 * @param root 
 */
 const flatten = (root: TreeNode | null): void => {
    // 判空
    if (root === null) return;

    flatten(root.left)
    flatten(root.right)

    // 构造关系
    const left = root.left
    const right = root.right

    root.left = null
    root.right = left;

    // 让出root的右孩子
    let p = root;
    while(p.right) { // 首次的p.right就是原来的左孩子, 一直找到没有右孩子为止
        p = p.right;
    }  
    // 指向右孩子
    p.right = right;
};



// 迭代
const flatten2 = (root: TreeNode | null): void => {
    // 判空
    if (root === null) return;


    while (root !== null) {
        if (root.left) {
            // 做孩子不为空, 获取左孩子的前驱节点
            const aced = getAced(root)!;

            if (aced.right === null) {
                // 前驱节点的右孩子为空, 让其右孩子指向当前的节点
                aced.right = root;
                root = root.left;
            } else {
                // 前驱节点的右孩子不为空, 说明等于当前节点, 现在改变指向
                // 构造链表
                const tmp: TreeNode = root.right!

                // 改变指向
                root.right = root.left
                root.left = null

                aced.right = tmp;

                root = tmp
            }
        } else {
            // 左孩子为空
            root = root.right;
        }
    }
};


/**
 * 获取节点n的前驱节点
 * @param n 
 */
const getAced = (n: TreeNode) => {
    let left = n.left;
    while (left && left.right && left.right !== n) {
        left = left.right;
    }
    return left;
}